public class BackPack2 {
    public int backPackII(int m, int[] a, int[] v) {
        int n = a.length;
        int[][] arr = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                //石头比背包空间小,选择放还是不放
                if(a[i - 1] <= j) {
                    arr[i][j] = Math.max(arr[i - 1][j],arr[i - 1][j - a[i - 1]] + v[i - 1]);
                }else {
                    //石头比背包空间大
                    arr[i][j] = arr[i - 1][j];
                }
            }
        }
        return arr[n][m];
    }
}
